ABC 072 D - Derangement
Difficulty: 656
まず、$ O(N^2)以上の操作は不可能
また、最小回数を求めるために全ての場合を調べるのも指数時間かかる。（はず）
まずは実験
code:note
1 4 3 5 2
1 2 3 4 5
x x
4 1 3 5 2
4 1 5 3 2
code:note
9
1 2 4 9 5 8 7 3 6
1 2 3 4 5 6 7 8 9
x x x x
xに着目して入れ替えていくのがいいのか？
xは$ i = p_iとなってしまっているところを意味する。
これ以外のところに着目してしまったら余計に回数増えそうな気もする。
もしかしてDP...ではないか？
二つの場合は考えやすい
三つの場合は？
code:note
2 1 3
1 2 3
x
code:note
一つ一つ範囲を増加させて解くってことはできなくもなさそうだな
ただ、部分最適性が成り立つのか...？
不安になるポイント
xを目当てに揃えた結果、他のポイントで新しくxが現れないか？
どうだろ
そのような場合ってどんな時だ？
まず、xが現れるとはどこかのiでp_i == iとなることだが
あるjに注目して隣り合う二つの数をスワップした時に
p_{j+1} == jかp_{j-1} == jかp_{j} == j + 1かp_{j} == j - 1となるか？
となる場合が存在するか
これは存在しない
着目するjが必ずp_j == jを満たす。
順列pは同じ要素を二つ以上持たないので、
p_{j+1} == j p_{j-1} == j
p_{j} == j+1 p_{j} == j-1
のうち一個以上でも満たすことはない。
よって、xが生まれることはない。
つまり、操作を行うと必ずxが減る。
一個ずつ隣接せずxが並んでいる場合は
問題はxが二個ある場合とか、3個並んでる場合とか
p_j == j, p_{j+1} == {j+1}, p_{j+2} == j+2, ...
二個ずつ選んで操作するのが最適か？
p_j, p_{j+1}
最適みたい
一回の操作では高々連続した二個しかxが消えない
順列のうち二つの要素以外が変わることはない。
ので、仮にn個連続でxが並んでたとしても
それらを消し切るのには少なくとも(n+1)/2回かかる。
code:note
1 2 3 4 5 6
x x x x x x
code:note
9
1 2 4 9 5 8 7 3 6
1 2 3 4 5 6 7 8 9
x x x x
1 2 4 9 5 8 3 7 6
1 2 3 4 5 6 7 8 9
x x x
1 2 4 9 5 8 3 7 6
1 2 3 4 5 6 7 8 9
x x x
1 2 4 9 8 5 3 7 6
1 2 3 4 5 6 7 8 9
x x
2 1 4 9 8 5 3 7 6
2 1 3 4 5 6 7 8 9
一気に二つxも消える場合がある。
アルゴリズム
minimum_count = 0
前からpを一度読み取る（ループ変数i）
combo = 0と定義する。
もしi + 1 == A[i]であれば
combo += 1
そうでなければ
minimum_count += (combo + 1) / 2
combo = 0
（切り上げ）
minimum_countを出力する。
bugfix 端処理
最後までxが引き続いたときに答えに加算されていない。
なぜ気づけなかったのか
全てのxの連続した区間に対して、"右端"が存在すると思い込んでいたため
if文がどの範囲で実行されるかについて検証が必要だった。
擬似的な実行例
code:cpp
9
1 2 4 9 5 8 7 3 6
^ ^ ^ ^
combo = 2 -> 3 / 2 = 1: min_count = 1
combo = 1 -> 2 / 2 = 1: min_count = 2
combo = 1 -> 2 / 2 = 1: min_count = 2
問題例を手で実行し通すべきだったかも...。